/*
 * (C) Copyright 2014-2018, by Dimitrios Michail
 *
 * JHeaps Library
 * 
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.jheaps.monotone

import junit.framework.TestCase.assertEquals
import org.jheaps.AddressableHeap
import org.junit.Assert
import org.junit.Test
import java.io.*
import java.math.BigInteger
import java.util.*

class BigIntegerRadixAddressableHeapTest {
    @Test
    fun testBug2() {
        val h: AddressableHeap<BigInteger, Void> =
            BigIntegerRadixAddressableHeap(BigInteger.ZERO, BigInteger.valueOf(100))
        h.insert(BigInteger.ZERO)
        assertEquals(BigInteger.ZERO, h.findMin().key)
        assertEquals(BigInteger.ZERO, h.deleteMin().key)
        h.insert(BigInteger.valueOf(15))
        assertEquals(BigInteger.valueOf(15), h.findMin().key)
    }

    @Test
    fun testVerySmall() {
        val h: AddressableHeap<BigInteger, Void> = BigIntegerRadixAddressableHeap(
            BigInteger.valueOf(29),
            BigInteger.valueOf(36)
        )

        h.insert(BigInteger.valueOf(29))
        h.insert(BigInteger.valueOf(30))
        h.insert(BigInteger.valueOf(31))
        h.insert(BigInteger.valueOf(30))
        h.insert(BigInteger.valueOf(33))
        h.insert(BigInteger.valueOf(36))
        h.insert(BigInteger.valueOf(35))

        Assert.assertEquals(h.size(), 7)
        assertEquals(h.findMin().key, BigInteger.valueOf(29))
        Assert.assertEquals(h.size(), 7)
        assertEquals(h.deleteMin().key, BigInteger.valueOf(29))
        Assert.assertEquals(h.size(), 6)
        assertEquals(h.findMin().key, BigInteger.valueOf(30))
        assertEquals(h.deleteMin().key, BigInteger.valueOf(30))
        assertEquals(h.findMin().key, BigInteger.valueOf(30))
        assertEquals(h.deleteMin().key, BigInteger.valueOf(30))
        assertEquals(h.findMin().key, BigInteger.valueOf(31))
        assertEquals(h.deleteMin().key, BigInteger.valueOf(31))
        assertEquals(h.findMin().key, BigInteger.valueOf(33))
        assertEquals(h.deleteMin().key, BigInteger.valueOf(33))
        assertEquals(h.findMin().key, BigInteger.valueOf(35))
        assertEquals(h.deleteMin().key, BigInteger.valueOf(35))
        assertEquals(h.findMin().key, BigInteger.valueOf(36))
        assertEquals(h.deleteMin().key, BigInteger.valueOf(36))
        Assert.assertEquals(h.size(), 0)
        Assert.assertTrue(h.isEmpty)
    }

    @Test
    fun test() {
        val h: AddressableHeap<BigInteger, Void> = BigIntegerRadixAddressableHeap(BigInteger.valueOf(0), SIZE)

        for (i in 0 until SIZE.toInt()) {
            h.insert(BigInteger.valueOf(i.toLong()))
            assertEquals(BigInteger.ZERO, h.findMin().key)
            Assert.assertFalse(h.isEmpty)
            Assert.assertEquals(h.size(), (i + 1).toLong())
        }

        for (i in SIZE.toInt() - 1 downTo 0) {
            assertEquals(SIZE.subtract(BigInteger.valueOf((i + 1).toLong())), h.findMin().key)
            h.deleteMin()
        }
    }

    @Test
    fun testSortRandomSeed1() {
        val h: AddressableHeap<BigInteger, Void> = BigIntegerRadixAddressableHeap(
            BigInteger.valueOf(0),
            SIZE.add(BigInteger.ONE)
        )

        val generator = Random(1)

        val a = LongArray(SIZE.toInt())
        for (i in 0 until SIZE.toInt()) {
            a[i] = (SIZE.toLong() * generator.nextDouble()).toLong()
        }
        Arrays.sort(a)
        for (i in 0 until SIZE.toInt()) {
            h.insert(BigInteger.valueOf(a[i]))
        }

        var prev: BigInteger? = null
        var cur: BigInteger
        while (!h.isEmpty) {
            cur = h.findMin().key
            h.deleteMin()
            if (prev != null) {
                Assert.assertTrue(prev.compareTo(cur) <= 0)
            }
            prev = cur
        }
    }

    @Test
    fun testMonotoneOkOnLastDeleted() {
        val h: AddressableHeap<BigInteger, Void> = BigIntegerRadixAddressableHeap(
            BigInteger.ZERO,
            BigInteger.valueOf(100)
        )
        h.insert(BigInteger.valueOf(100L))
        assertEquals(BigInteger.valueOf(100L), h.findMin().key)
        h.insert(BigInteger.valueOf(99L))
        assertEquals(BigInteger.valueOf(99L), h.findMin().key)
    }

    @Test(expected = IllegalArgumentException::class)
    fun testMonotoneNotOkOnLastDeleted() {
        val h: AddressableHeap<BigInteger, Void> = BigIntegerRadixAddressableHeap(
            BigInteger.ZERO,
            BigInteger.valueOf(100)
        )
        h.insert(BigInteger.valueOf(100L))
        h.deleteMin()
        h.insert(BigInteger.valueOf(99L))
    }

    @Test(expected = IllegalArgumentException::class)
    fun testIllegalConstruction() {
        BigIntegerRadixAddressableHeap<Void>(BigInteger.ZERO.subtract(BigInteger.ONE), BigInteger.valueOf(100))
    }

    @Test(expected = IllegalArgumentException::class)
    fun testIllegalConstruction1() {
        BigIntegerRadixAddressableHeap<Void>(BigInteger.valueOf(100), BigInteger.valueOf(99))
    }

    /*@Test(expected = IllegalArgumentException::class)
    fun testIllegalConstruction2() {
        BigIntegerRadixAddressableHeap<Void>(null, BigInteger.valueOf(99))
    }

    @Test(expected = IllegalArgumentException::class)
    fun testIllegalConstruction3() {
        BigIntegerRadixAddressableHeap<Void>(BigInteger.valueOf(99), null)
    }*/

    @Test
    fun testSameMinMax() {
        val h: AddressableHeap<BigInteger, Void> = BigIntegerRadixAddressableHeap(BigInteger.ONE, BigInteger.ONE)

        for (i in 0..14) {
            h.insert(BigInteger.valueOf(1))
        }

        Assert.assertEquals(15, h.size())
        for (i in 0..14) {
            assertEquals(BigInteger.ONE, h.deleteMin().key)
        }
        Assert.assertEquals(0, h.size())
    }

    @Test
    fun testBigDifference() {
        val longMax = BigInteger.valueOf(Long.MAX_VALUE)
        val bigValue = longMax.multiply(longMax)
        val h: AddressableHeap<BigInteger, Void> = BigIntegerRadixAddressableHeap(BigInteger.ZERO, bigValue)

        h.insert(BigInteger.ZERO)
        h.insert(longMax)
        h.insert(bigValue)

        Assert.assertEquals(3, h.size())
        assertEquals(BigInteger.ZERO, h.deleteMin().key)
        assertEquals(longMax, h.deleteMin().key)
        assertEquals(bigValue, h.deleteMin().key)
        Assert.assertEquals(0, h.size())
    }

    @Test
    fun testDelete() {
        val h: AddressableHeap<BigInteger, Void> = BigIntegerRadixAddressableHeap(
            BigInteger.valueOf(0),
            BigInteger.valueOf(15)
        )

        val array: Array<AddressableHeap.Handle<BigInteger, Void>> = Array(15){i->h.insert(BigInteger.valueOf(i.toLong()))}
        /*array = arrayOfNulls<AddressableHeap.Handle<*, *>>(15)
        for (i in 0..14) {
            array[i] = h.insert(BigInteger.valueOf(i.toLong()))
        }*/

        array[5].delete()
        assertEquals(BigInteger.valueOf(0), h.findMin().key)
        array[7].delete()
        assertEquals(BigInteger.valueOf(0), h.findMin().key)
        array[0].delete()
        assertEquals(BigInteger.valueOf(1), h.findMin().key)
        array[2].delete()
        assertEquals(BigInteger.valueOf(1), h.findMin().key)
        array[1].delete()
        assertEquals(BigInteger.valueOf(3), h.findMin().key)
        array[3].delete()
        assertEquals(BigInteger.valueOf(4), h.findMin().key)
        array[9].delete()
        assertEquals(BigInteger.valueOf(4), h.findMin().key)
        array[4].delete()
        assertEquals(BigInteger.valueOf(6), h.findMin().key)
        array[8].delete()
        assertEquals(BigInteger.valueOf(6), h.findMin().key)
        array[11].delete()
        assertEquals(BigInteger.valueOf(6), h.findMin().key)
        array[6].delete()
        assertEquals(BigInteger.valueOf(10), h.findMin().key)
        array[12].delete()
        assertEquals(BigInteger.valueOf(10), h.findMin().key)
        array[10].delete()
        assertEquals(BigInteger.valueOf(13), h.findMin().key)
        array[13].delete()
        assertEquals(BigInteger.valueOf(14), h.findMin().key)
        array[14].delete()
        Assert.assertTrue(h.isEmpty)
    }

    @Test
    fun testDelete1() {
        val h: AddressableHeap<BigInteger, Void> = BigIntegerRadixAddressableHeap(
            BigInteger.valueOf(0),
            BigInteger.valueOf(10)
        )

        val array: Array<AddressableHeap.Handle<BigInteger, Void>> = Array(8){i->h.insert(BigInteger.valueOf(i.toLong()))}
       /* array = arrayOfNulls<AddressableHeap.Handle<*, *>>(8)
        for (i in 0..7) {
            array[i] = h.insert(BigInteger.valueOf(i.toLong()))
        }*/

        array[5].delete()
        assertEquals(BigInteger.valueOf(0), h.findMin().key)
        array[7].delete()
        assertEquals(BigInteger.valueOf(0), h.findMin().key)
        array[0].delete()
        assertEquals(BigInteger.valueOf(1), h.findMin().key)
        array[2].delete()
        assertEquals(BigInteger.valueOf(1), h.findMin().key)
        array[1].delete()
        assertEquals(BigInteger.valueOf(3), h.findMin().key)
    }

    @Test
    fun testAddDelete() {
        val h: AddressableHeap<BigInteger, Void> = BigIntegerRadixAddressableHeap(BigInteger.ZERO, SIZE)

        val array: Array<AddressableHeap.Handle<BigInteger, Void>> = Array(SIZE.toInt()){i->h.insert(BigInteger.valueOf(i.toLong()))}
        /*array = arrayOfNulls<AddressableHeap.Handle<*, *>>(SIZE.toInt())
        for (i in 0 until SIZE.toInt()) {
            array[i] = h.insert(BigInteger.valueOf(i.toLong()))
        }*/

        for (i in SIZE.toInt() - 1 downTo 0) {
            array[i].delete()
            if (i > 0) {
                assertEquals(BigInteger.valueOf(0), h.findMin().key)
            }
        }
        Assert.assertTrue(h.isEmpty)
    }

    @Test
    fun testClear() {
        val h: AddressableHeap<BigInteger, Void> = BigIntegerRadixAddressableHeap(
            BigInteger.ZERO,
            BigInteger.valueOf(15)
        )

        for (i in 0..14) {
            h.insert(BigInteger.valueOf(i.toLong()))
        }

        h.clear()
        Assert.assertEquals(0L, h.size())
        Assert.assertTrue(h.isEmpty)
    }

    @Test(expected = IllegalArgumentException::class)
    fun testDeleteTwice() {
        val h: AddressableHeap<BigInteger, Void> = BigIntegerRadixAddressableHeap(
            BigInteger.ZERO,
            BigInteger.valueOf(15)
        )

        val array: Array<AddressableHeap.Handle<BigInteger, Void>> = Array(15){i->h.insert(BigInteger.valueOf(i.toLong()))}
        /*array = arrayOfNulls<AddressableHeap.Handle<*, *>>(15)
        for (i in 0..14) {
            array[i] = h.insert(BigInteger.valueOf(i.toLong()))
        }*/

        array[5].delete()
        assertEquals(BigInteger.valueOf(0), h.findMin().key)
        array[7].delete()
        assertEquals(BigInteger.valueOf(0), h.findMin().key)
        array[0].delete()
        assertEquals(BigInteger.valueOf(1), h.findMin().key)
        array[2].delete()
        assertEquals(BigInteger.valueOf(1), h.findMin().key)
        array[1].delete()
        assertEquals(BigInteger.valueOf(3), h.findMin().key)
        array[3].delete()
        assertEquals(BigInteger.valueOf(4), h.findMin().key)
        array[9].delete()
        assertEquals(BigInteger.valueOf(4), h.findMin().key)
        array[4].delete()
        assertEquals(BigInteger.valueOf(6), h.findMin().key)

        // again
        array[2].delete()
    }

    @Test(expected = IllegalArgumentException::class)
    fun testDeleteMinDeleteTwice() {
        val h: AddressableHeap<BigInteger, Void> = BigIntegerRadixAddressableHeap(
            BigInteger.ZERO,
            BigInteger.valueOf(100)
        )
        val e1 = h.insert(BigInteger.valueOf(50))
        h.insert(BigInteger.valueOf(100))
        h.deleteMin()
        e1.delete()
    }

    @Test(expected = IllegalArgumentException::class)
    fun testDeleteMinDeleteTwice1() {
        val h: AddressableHeap<BigInteger, Void> = BigIntegerRadixAddressableHeap(
            BigInteger.valueOf(99),
            BigInteger.valueOf(200)
        )

        for (i in 100..199) {
            h.insert(BigInteger.valueOf(i.toLong()))
        }

        h.deleteMin().delete()
    }

    @Test(expected = IllegalArgumentException::class)
    fun testDeleteMinDecreaseKey() {
        val h: AddressableHeap<BigInteger, Void> = BigIntegerRadixAddressableHeap(
            BigInteger.valueOf(100),
            BigInteger.valueOf(200)
        )

        for (i in 100..199) {
            h.insert(BigInteger.valueOf(i.toLong()))
        }
        h.deleteMin().decreaseKey(BigInteger.ZERO)
    }

    @Test
    fun testDecreaseKey() {
        val h: AddressableHeap<BigInteger, Void> = BigIntegerRadixAddressableHeap(
            BigInteger.ZERO,
            BigInteger.valueOf(200)
        )

        h.insert(BigInteger.ZERO) // monotone

        val array: Array<AddressableHeap.Handle<BigInteger, Void>> = Array(15){i->h.insert(BigInteger.valueOf(i.toLong()).add(BigInteger.valueOf(100)))}
       // array = arrayOfNulls<AddressableHeap.Handle<*, *>>(15)

        /*for (i in 0..14) {
            array[i] = h.insert(BigInteger.valueOf(i.toLong()).add(BigInteger.valueOf(100)))
        }*/

        array[5].decreaseKey(BigInteger.valueOf(5))
        array[1].decreaseKey(BigInteger.valueOf(50))
        array[10].decreaseKey(BigInteger.valueOf(3))
        array[0].decreaseKey(BigInteger.valueOf(1))
        array[5].delete()
        array[2].delete()
        array[11].delete()
        array[9].delete()

        assertEquals(BigInteger.valueOf(0), h.deleteMin().key)
        assertEquals(BigInteger.valueOf(1), h.deleteMin().key)
        assertEquals(BigInteger.valueOf(3), h.deleteMin().key)
        assertEquals(BigInteger.valueOf(50), h.deleteMin().key)
        assertEquals(BigInteger.valueOf(103), h.deleteMin().key)
        assertEquals(BigInteger.valueOf(104), h.deleteMin().key)

        array[14].decreaseKey(BigInteger.valueOf(111))
        array[13].decreaseKey(BigInteger.valueOf(109))

        assertEquals(BigInteger.valueOf(106), h.deleteMin().key)
        assertEquals(BigInteger.valueOf(107), h.deleteMin().key)
        assertEquals(BigInteger.valueOf(108), h.deleteMin().key)
        assertEquals(BigInteger.valueOf(109), h.deleteMin().key)
        assertEquals(BigInteger.valueOf(111), h.deleteMin().key)
        assertEquals(BigInteger.valueOf(112), h.deleteMin().key)
    }

    @Test(expected = IllegalArgumentException::class)
    fun testIncreaseKey() {
        val h: AddressableHeap<BigInteger, Void> = BigIntegerRadixAddressableHeap(
            BigInteger.ZERO,
            BigInteger.valueOf(200)
        )

        val array: Array<AddressableHeap.Handle<BigInteger, Void>>  = Array(15){i->h.insert(BigInteger.valueOf(i.toLong()).add(BigInteger.valueOf(100)))}
        /*array = arrayOfNulls<AddressableHeap.Handle<*, *>>(15)
        for (i in 0..14) {
            array[i] = h.insert(BigInteger.valueOf(i.toLong()).add(BigInteger.valueOf(100)))
        }*/

        assertEquals(BigInteger.valueOf(100), h.findMin().key)
        array[5].decreaseKey(BigInteger.valueOf(5))
        assertEquals(BigInteger.valueOf(5), h.findMin().key)
        array[1].decreaseKey(BigInteger.valueOf(102))
    }

    @Test
    @Throws(IOException::class, ClassNotFoundException::class)
    fun testSerializable() {
        var h: AddressableHeap<BigInteger, Void> = BigIntegerRadixAddressableHeap<Void>(
            BigInteger.ZERO,
            BigInteger.valueOf(15)
        )

        for (i in 0..14) {
            h.insert(BigInteger.valueOf(i.toLong()))
        }

        // write
        val baos = ByteArrayOutputStream()
        val oos = ObjectOutputStream(baos)
        oos.writeObject(h)
        oos.close()
        val data = baos.toByteArray()

        // read
        val ois = ObjectInputStream(ByteArrayInputStream(data))
        val o = ois.readObject()
        ois.close()
        h = o as AddressableHeap<BigInteger, Void>

        for (i in 0..14L) {
            Assert.assertEquals(15 - i, h.size())
            assertEquals(BigInteger.valueOf(i), h.findMin().key)
            h.deleteMin()
        }
        Assert.assertTrue(h.isEmpty)
    }

    companion object {
        private val SIZE: BigInteger = BigInteger.valueOf(100000)
    }
}
